/**
 * 给你两个单词word1 和word2， 请返回将word1转换成word2 所使用的最少操作数 。
 *
 * 你可以对一个单词进行如下三种操作：
 *
 * 插入一个字符
 * 删除一个字符
 * 替换一个字符
 * 链接：https://leetcode.cn/problems/edit-distance
 * 题解：https://labuladong.gitee.io/algo/3/26/75/
 */
class MinDistance {
    /**
     * 法一：递归，没有剪掉重复的子问题，在leetcode会超时,看后面还有两个优化版本
     * @param word1
     * @param word2
     * @return
     */
    public int minDistanceDiGui(String word1, String word2) {
        int n=word1.length();
        int m=word2.length();
        return dp(word1,n-1,word2,m-1);
    }
    public int dp(String s1,int i,String s2,int j) {
        if(i==-1) {
            return j+1;
        }
        if(j==-1) {
            return i+1;
        }
        if(s1.charAt(i)==s2.charAt(j)) {
            return dp(s1,i-1,s2,j-1);
        } else {
            return min (dp(s1,i,s2,j-1)+1,//插入
                        dp(s1,i-1,s2,j)+1,//删除
                        dp(s1,i-1,s2,j-1)+1//替换
            );
        }
    }

    /**
     * 法二：用备忘录数组记录重复出现的子问题进行剪枝，相当于动态规划了
     */
    int[][] memo;
    public int minDistanceDiGuiMemo(String word1, String word2) {
        int n=word1.length();
        int m=word2.length();
        memo=new int[n][m];
        for(int[] row:memo) {
            Arrays.fill(row,-1);
        }
        return dpMemo(word1,n-1,word2,m-1);
    }
    public int dpMemo(String s1,int i,String s2,int j) {
        if(i==-1) {
            return j+1;
        } 
        if(j==-1) {
            return i+1;
        }
        if(memo[i][j]!=-1) {
            return memo[i][j];
        }
        if(s1.charAt(i)==s2.charAt(j)) {
            memo[i][j]=dpMemo(s1,i-1,s2,j-1);
        } else {
            memo[i][j]=min(//三种操作取最小
                        dpMemo(s1,i,s2,j-1)+1,//插入
                        dpMemo(s1,i-1,s2,j)+1,//删除
                        dpMemo(s1,i-1,s2,j-1)+1//替换
            );
        }
        return memo[i][j];
    }
    public int minDistance(String word1, String word2) {
        int n=word1.length();
        int m=word2.length();
       return dpTable(word1,word2);
        
    }

    /**
     * 法三：正常的动态规划，前面两种的递归是自顶向下，法三则是自底向上
     * 法三的状态转移方程可以说是从上面的递归得到启发推导的，法二和法三时间复杂度差不多，都算动态规划
     *  * /*
     *      *  F(i,j):word1的前i个字符变成word2的前j个字符的编辑距离
     *      *
     *      * 状态递推：
     *      *  F(i,j) = min { F(i-1,j）+1, F(i,j-1) +1, F(i-1,j-1) +(w1[i]==w2[j]?0:1) }
     *      *  上式表示从删除，增加和替换操作中选择一个最小操作数
     *      *  F(i-1,j): w1[1,...,i-1]于w2[1,...,j]的编辑距离，删除w1[i]的字符--->F(i,j)
     *      *  F(i,j-1): w1[1,...,i]于w2[1,...,j-1]的编辑距离，增加一个字符--->F(i,j)
     *      *  F(i-1,j-1): w1[1,...,i-1]于w2[1,...,j-1]的编辑距离，如果w1[i]与w2[j]相同，
     *      *  不做任何操作，编辑距离不变，如果w1[i]与w2[j]不同，替换w1[i]的字符为w2[j]--->F(i,j)
     *      *
     *      * 初始化：
     *      *  初始化一定要是确定的值，如果这里不加入空串，初始值无法确定
     *      *  F(i,0) = i :word与空串的编辑距离，删除操作
     *      *  F(0,i) = i :空串与word的编辑距离，增加操作
     *      *
     *      * 返回结果：F(m,n)
     * @param s1
     * @param s2
     * @return
     */
    public int dpTable(String s1,String s2) {
        int n=s1.length();
        int m=s2.length();
        int[][] dp=new int[n+1][m+1];
        for(int i=0;i<=m;i++) {
            dp[0][i]=i;
        }
        for(int j=0;j<=n;j++) {
            dp[j][0]=j;
        }
        for(int i=1;i<=n;i++) {
            for(int j=1;j<=m;j++) {
                if(s1.charAt(i-1)==s2.charAt(j-1)) {
                    dp[i][j]=dp[i-1][j-1];
                }
                else {
                    dp[i][j]=min(
                        dp[i][j-1]+1,//插入
                        dp[i-1][j]+1,//删除
                        dp[i-1][j-1]+1//替换
                );
                }
            }
        }
        return dp[n][m];
    }
    public int min(int a,int b,int c) {
        return Math.min(a,Math.min(b,c));
    }
}